import java.util.Arrays;

public class Leet931 {
    public static void main(String[] args) {
        Leet931 l = new Leet931();
        System.out.println(l.minFallingPathSum(new int[][]{{-19,57},{-40,-5}}));
    }
    public int minFallingPathSum(int[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length+2];
        for (int i = 0; i < dp.length; i++)
            for (int j = 0; j < dp[0].length; j++)
                dp[i][j] = Integer.MAX_VALUE;
        System.arraycopy(matrix[0], 0, dp[0], 1, matrix[0].length);
        for (int i = 1; i < dp.length; i++)
            for (int j = 1; j < dp[0].length-1; j++)
                dp[i][j] = matrix[i][j-1]+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]));
        int min = Integer.MAX_VALUE;
        for (int i : dp[dp.length - 1])
            min = Math.min(i,min);
        return min;
    }
}
